unit stlmain;

interface
uses Stl_types, stl_base;
function Less(var a, b:StlType): boolean;overload;
function Equal(const a, b: StlType): boolean;
function bsearch(const l, r:Iterator; const key:STLTYPE):Iterator;
procedure swp(var a, b:STLTYPE);
procedure qsort(var ar:Container; var l, r:Iterator);overload;
procedure qsort(var ar:Container); overload;
implementation
function Less(var a, b:StlType): boolean;

begin
  //Less := a < b;
end;

procedure swp(var a, b:STLTYPE);
var
  t:STLTYPE;
begin
  t := a;
  a := b;
  b := t;
end;

function Equal(const a, b: StlType): boolean;
begin
  {Equal := ((@a.p_init = @b.p_init) and (@a.p_run = @b.p_run)
  and (@a.p_free = @b.p_free));   }
  Equal := (a = b)  
end;

function bsearch(const l, r:Iterator; const key:STLTYPE):Iterator;
var
  i, j :Iterator;
  m:Iterator;
begin
  i := L;
  j := r;
  if (l = nil)or (r = nil) then exit;
  while (i^.id < j^.id) do
  begin
   // m := (i^.id+j^.id) div 2;
    if Less(m^.data, j^.data) then
      i := m
    else
      j := m;
  end;
 if Equal(i^.data, key) then
    bsearch := i
  else
    if Equal(j^.data,key) then
      bsearch := j
    else
      bsearch := nil;
  bsearch := i;
end;

procedure qsort(var ar:Container; var l, r:Iterator); overload;
  procedure sort(const _left, _right: Iterator);
  var
    I, J: Iterator;
    mid: STLTYPE;
  begin
    i := _Left;
    j := _Right;
    if (_left = nil)or (_right = nil) then exit;
    mid := ar.get((i^.id + j^.id) div 2);
    while (i^.id < j^.id) do
    begin
      while (i <> nil) and(Less(i^.data, mid)) do i := i^.next;
      while (j <> nil) and(Less(mid, j^.data)) do j := j^.prev;
      if (i^.id <= j^.id)and(i <> nil) and(j <> nil) then
      begin
	      swp(i^.data, j^.data);
	      i := i^.next;
	      j := j^.prev;
      end;
    end;
    if ( i^.id< _right^.id) then sort(i, _right);
    if (_left^.id < j^.id) then sort(_left, j);
  end;
begin
  if (ar.Empty) then exit;
  if (ar.find(l)) and(ar.find(l)) then
    sort(l, r);
  //ar.sorted := true;
end;

procedure qsort(var ar: Container);  overload;
var
  a_begin, a_end: Iterator;
begin
  a_begin := ar._Begin;
  a_end := ar._END;
  qsort(ar, a_begin, a_end);
end;

end.
